package search;

import java.util.Arrays;

public class Matrix {

	public static boolean doesElementExist(int[][] matrix, int element){

		int numRow = matrix.length; // number of rows
		int numColumn = matrix[0].length; // number of columns, assuming every row has same number of columns
		
		// find the most efficient way
		int min1 = numRow + numColumn;
		int min2 = (numRow > numColumn) ? (int)(numColumn*((Math.log(numRow))/(Math.log(2)))) : (int)(numRow*((Math.log(numColumn))/(Math.log(2))));
		
		System.out.println("min1: "+min1);
		System.out.println("min2: "+min2);

		if(min1 < min2){
			System.out.println("linearSearch called");
			return linearSearch(matrix, numRow, numColumn, element);
		}else{
			System.out.println("binarySearch called");
			return binarySearch(matrix, numRow, numColumn, element);
		}
	}
	
	// timing complexity O(n + m)
	// n is numRow and m is numColumn
	private static boolean linearSearch(int[][] matrix, int numRow, int numColumn, int element){
		int currentRow = numRow - 1;
		int currentColumn = 0;
		int currentElement = 0;
		
		while(currentRow >= 0 && currentColumn < numColumn){

			currentElement = matrix[currentRow][currentColumn];
			
			if(element == currentElement){ // element found
				return true;
			}else if(element < currentElement){ // element is smaller than current element, so move upwards
				currentRow--;
			}else{ // element is greater than current element, so move rightwards
				currentColumn++;
			}
		}
		
		return false;
	}

	// timing complexity O(n * log m)
	// where n is smaller of numRow and numColumn
	private static boolean binarySearch(int[][] matrix, int numRow, int numColumn, int element){
		
		boolean isNumRowSmaller = numRow > numColumn ? false : true;
		int numSmaller = numRow > numColumn ? numColumn : numRow;
		
		// wrapper to extract columns of 2d array
		ColumnExtractor columnExtractor = new ColumnExtractor(matrix);
	
		int found = -1;
		
		while(numSmaller > 0){
			if(isNumRowSmaller){
				found = Arrays.binarySearch(matrix[--numSmaller], element);
			}else{
				found = Arrays.binarySearch(columnExtractor.getColumn(--numSmaller), element);
			}
			
			if(found >= 0){
				return true;
			}
		}
		
		return false;
	}
}


// this class is a wrapper to get the column of a matrix
// assumption: every row has same number of element
class ColumnExtractor{
	
	private int[][] matrix;
	private int numColumn;
	private int numRow;
	
	public ColumnExtractor(int[][] matrix){
		this.matrix = matrix;
		this.numColumn = matrix[0].length;
		this.numRow = matrix.length;
	}

	// indexColumn is zero-based
	public int[] getColumn(int indexColumn){
		if(indexColumn >= numColumn){
			throw new ArrayIndexOutOfBoundsException();
		}
		
		int[] column = new int[numRow];
		int currentRow = 0;
		while(currentRow < numRow){
			column[currentRow] = matrix[currentRow][indexColumn];
			currentRow++;
		}
		
		return column;
	}
	
	
}